先前看到了常見執行時間的圖形，線條越平代表演算法速度越快，越陡則代表越慢。

我們會發現O(log n)的二分搜尋其實算是數一數二快速的演算法，不過二分搜尋的條件是只能在有序陣列中施行，這也代表陣列是否有排序有時相當重要，所以也有許多的演算法在解決排序(sorting)的問題。

如果今天有七張蓋起來的撲克牌，隨意放在桌上，一次只能打開一張檢查。要怎麼樣讓這些牌由小到大排好呢？

最直接的方法，可能就是一張一張找出最小的牌。我們打開最左邊第一張，接著依序打開後面的牌跟它比較，如果發現比較小的牌，就交換位置，把較小的牌換到第一張，接這用這張牌繼續比較，如下面的例子：

3, 6, 2, 7, 1, 4, 5
// 打開第一張，3即是目前最小的牌。以3依序跟後面的數字比，比到2時發現2較小，把2換到第一個。

2, 6, 3, 7, 1, 4, 5
// 接這用2繼續跟7比，再跟1比，發現1較小，把1換到第一個位置。

1, 6, 3, 7, 2, 4, 5
// 接著用1繼續跟最後的4和5比，1仍然是最小，留在第一位。

用這樣的方式比較完一輪後，可以確定的是最小的牌會在第一個位置，那麼可以說第一個位置已經排序完成，不用再檢查或移動了。接著從第二個位置開始，進行跟剛剛一樣的比較，全部比完後，第二個位置也排好了，再從第三個位置開始...

1, 2, 6, 7, 3, 4, 5
// 第二輪比完後的狀態

1, 2, 3, 7, 6, 4, 5
// 第三輪比完後的狀態

像這樣比較下來，等於每一輪會排好一個數字，那麼比到最後一輪剩下一個數字時，就會完成排序。

這樣的演算法叫做選擇排序，它的步驟其實就是不斷地從未排序的元素中選出最小(或最大)的，排在排序好的數列末尾，直到所有數字都排序完成。

不過從剛剛的例子中大概也可以感覺得出來，這種直觀的演算法速度頗慢。可以把它想成當總共有n個元素，就得比較n輪，每一輪又得全部元素都檢查一遍，所以它的執行時間是O(n²)。[註1]

而且選擇排序還有一個缺點。因為一次只能檢查一個位置，所以任何數列都只能經過每一輪逐一比較，才能知道結果。也就是說，就算你給電腦一個有序陣列，選擇排序還是無法加快，無論如何得經過n²次操作，等於執行時間最糟是O(n²)，最佳還是Ω(n²)。

以下是選擇排序的動畫，紅色是當前最小的元素，黃色是已經排序好的元素：

圖片來源：維基百科

同樣是排序，下一回我們會看到思考方式不太一樣的泡沫排序演算法。

• [註1]嚴格來說，因為每一輪會排好一個數字，所以每一輪需要檢查的元素會減一，總共檢查的次數是n+(n-1)+(n-2)+...+1，這個總和是(n²+n)/2，執行時間仍是O(n²)。